//
// Created by Senhai Xu on 2025/3/5.
//
//
// Created by Senhai Xu on 2025/3/5.
//
//链表内指定区间反转
#include <iostream>
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     * 1->2->3->4->5
     */
    ListNode* ReverseListBetween(ListNode* head,int m,int n) {
        if (head == nullptr || head->next == nullptr) return head;
//       定义虚拟头结点，处理m=1时头结点变化的情况
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* pre = dummy;
//        定位到m的前一个结点
        for (int i = 0; i < m - 1; i++) {
            pre = pre->next;
        }
        ListNode* curr = pre->next;
        ListNode* curr_next ;
//        将m到n的区间进行头插法
        for (int i = 0; i < n - m; i++){
            curr_next = curr->next;
            curr->next = curr_next->next;
            curr_next->next = pre->next;
            pre->next = curr_next;
        }
        return dummy->next;




//        ListNode* tail = curr;
////        定位到反转区间的最后一个节点
//        for(int i = 0; i < n - m ; i++){
//            tail = tail->next;
//        }
////        切分
//        ListNode* next = tail->next;
//        pre->next = nullptr;
//        tail->next = nullptr;
//        ListNode* ans = ReverseList(curr);
////        头部重连
//        pre->next = ans;
////        尾部重连
//        curr->next = next;
//        return dummy->next;

    };
private:
    ListNode* ReverseList(ListNode* head){
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* ans = ReverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return  ans;
    };

};

// 辅助函数：打印链表
void printList(ListNode* head) {
    ListNode* curr = head;
    while (curr != nullptr) {
        std::cout << curr->val << " ";
        curr = curr->next;
    }
    std::cout << std::endl;
}
